/**
 * @file BST.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-15
 * 
 * @copyright Copyright (c) 2021
 * 
 * 二叉搜索树 BinarySearchTree
 * 54.BST的第k大节点
 * 68.I.BST的最近公共祖先
 */

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val = 0, TreeNode *left = nullptr, TreeNode *right = nullptr)
        : val(val), left(left), right(right) {}
};

class Solution
{
public:
    // 54.BST的第k大节点
    int kthLargest(TreeNode *root, int k)
    {
        // 中序遍历的逆序，遍历到第k个元素即可
        traversal(root, k);
        return res;
    }

private:
    int cnt = 0;
    int res;
    void traversal(TreeNode *root, int k)
    {
        if (root == nullptr) {
            return;
        }
        traversal(root->right, k);
        ++cnt;
        if (cnt == k) {
            res = root->val;
            return;
        }
        traversal(root->left, k);
    }

public:
    // 68.I 
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        if (root == nullptr) {
            return root;
        } else if (root->val < p->val && root->val < q->val) {
            return lowestCommonAncestor(root->right, p, q);
        } else if (root->val > p->val && root->val > q->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else {
            return root;
        }
    }
};